Skip to main content

Greedy

Pattern

Adjacent Selection​

When you need to find minimum/maximum differences between any two elements in a subset of the array => Sorting the array helps because the minimum diff between any two chosen elements will always occur between adjacent elements in the sorted arrays

  • In the sorted array, when we're selecting elements with a minimum difference requirement, we can make locally optimal choices that lead to a globally optimal solution. Here's why:

  • For a given target difference T, our greedy strategy is:

  1. Take the first element
  2. Take the next element that gives us at least difference T
  3. Keep doing this until we either get k elements (success) or run out of elements (failure)
  • This is greedy because at each step, we take the earliest possible element that maintains our minimum difference requirement. We don't need to consider any other choices because:
  1. If we skip an eligible element and take a later one instead, we're not improving our minimum difference (since we sorted the array)
  2. Taking a later element only reduces our remaining choices for subsequent selections

https://leetcode.com/problems/minimum-difference-between-highest-and-lowest-of-k-scores

https://leetcode.com/problems/maximum-product-difference-between-two-pairs/

https://leetcode.com/problems/minimum-absolute-difference/

https://leetcode.com/problems/maximum-points-you-can-obtain-from-cards/

https://leetcode.com/problems/find-k-closest-elements

https://leetcode.com/problems/maximum-distance-between-a-pair-of-values

https://leetcode.com/problems/minimize-maximum-of-array

https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers

https://leetcode.com/problems/maximum-tastiness-of-candy-basket

 def maximumTastiness(self, price: List[int], k: int) -> int:
    price.sort()
    maxDiff = abs(price[-1] - price[0])

    def canPick(score):
        pick = []

        for p in price:
            if not pick or abs(p - pick[-1]) >= score:
                pick.append(p)
                if len(pick) >= k:
                    return True
        
        return False

    left, right = 0, maxDiff
    while left <= right:
        mid = left + (right-left)//2
        if canPick(mid):
            left = mid + 1
        else:
            right = mid - 1

    return left - 1

https://leetcode.com/problems/divide-intervals-into-minimum-number-of-groups

https://leetcode.com/problems/put-marbles-in-bags

https://leetcode.com/problems/maximum-number-of-tasks-you-can-assign

https://leetcode.com/problems/minimum-initial-energy-to-finish-tasks

https://leetcode.com/problems/maximum-score-of-a-good-subarray/description/